#include <stdio.h>
#include "single_linked_list.cpp"

// 提取带头结点的两个递增链表的公共元素 不破坏两链表
LinkedList GetCommon(LinkedList &L1, LinkedList &L2)
{
    LinkedList res;
    InitList(res);
    LNode *tail = res; // 新链表尾指针
    LNode *ptr1 = L1->next, *ptr2 = L2->next;
    while (ptr1 != NULL && ptr2 != NULL)
    {
        if (ptr1->data == ptr2->data) {
            // 克隆结点 以确保不破坏原结点
            LNode *s = (LNode *) malloc(sizeof(LNode));
            s->data = ptr1->data;
            s->next = NULL;
            // 更新新链表
            tail->next = s;
            tail = tail->next;
            // 继续判断之后的节点
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        } else if (ptr1->data < ptr2->data)
            ptr1 = ptr1->next;
        else 
            ptr2 = ptr2->next;
    }
    return res;
}

int main()
{
    LinkedList L1;
    InitList(L1);

    LinkedList L2;
    InitList(L2);

    // 插入
    ListAppend(L1, 0);
    ListAppend(L1, 3);
    ListAppend(L1, 7);
    ListAppend(L1, 10);
    PrintList(L1);

    ListAppend(L2, 1);
    ListAppend(L2, 2);
    ListAppend(L2, 5);
    ListAppend(L2, 10);
    PrintList(L2);

    LinkedList res = GetCommon(L1,L2);
    PrintList(L1);
    PrintList(L2);
    PrintList(res);

    return 0;
}